package main

import (
	"fmt"
	"math"
)

/*
*
解析:

	寻找以 root 为起点，所有可能路径的 sum 值中的最大值。
	借助辅助函数oneSide寻找最大边长度，oneside(root) = root.Val+max(0,max(oneside(root.Left),oneside(root.Right))),计算时需要对整个树进行遍历，遍历时可以计算每个以每个节点为根节点的子树的最大路径长度，其中最长值便是整个树的最大路径长度
*/
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func main() {
	root := TreeNode{Val: 0, Left: nil, Right: nil}
	left := TreeNode{Val: 2, Left: nil, Right: nil}
	right := TreeNode{Val: 3, Left: nil, Right: nil}
	root.Left = &left
	root.Right = &right
	left.Left = &TreeNode{Val: 4, Left: nil, Right: nil}
	left.Right = &TreeNode{Val: 5, Left: nil, Right: nil}
	fmt.Println(maxPathSum(&root))
}

func maxPathSum(root *TreeNode) int {
	if root == nil {
		return 0
	}
	max := math.MinInt32
	oneSide(root, &max)
	return max
}

// 返回以某节点为起点路径最大的一边的值
func oneSide(root *TreeNode, maxSum *int) int {
	if root == nil {
		return math.MinInt32
	}
	left := oneSide(root.Left, maxSum)
	right := oneSide(root.Right, maxSum)

	oneSideMax := max(max(left+root.Val, right+root.Val), root.Val)
	//在计算oneside的同时 计算以该节点为root的子树的最大值
	*maxSum = max(*maxSum, max(oneSideMax, left+right+root.Val))
	return oneSideMax
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

// v2
//func maxPathSum(root *TreeNode) int {
//	if root == nil {
//		return 0
//	}
//
//	maxSum := math.MinInt32
//	var helper func(root *TreeNode) int
//	helper = func(root *TreeNode) int {
//		if root == nil {
//			return 0
//		}
//
//		left := helper(root.Left)
//		right := helper(root.Right)
//
//		oneSideMax := max(max(root.Val+left, root.Val+right), root.Val)
//
//		maxSum = max(maxSum, max(oneSideMax, root.Val+left+right))
//		return oneSideMax
//	}
//	helper(root)
//	return maxSum
//}
